#include <iostream>
#include <string>
using namespace std;

void permute(string &str, int idx) {
  if (idx == str.size() - 1) {
    cout << str << endl;
    return;
  }

  auto swap = [&](int i) {
    auto tmp = str[idx];
    str[idx] = str[i];
    str[i] = tmp;
  };

  for (auto i = idx; i < str.size(); ++i) {
    swap(i);
    permute(str, idx + 1);
    swap(i);
  }
}

void combine(const string &str, string &sub_str, int idx) {
  if (idx == str.size()) {
    cout << sub_str << endl;
    return;
  }

  sub_str.push_back(str[idx]);
  combine(str, sub_str, idx + 1);
  sub_str.pop_back();

  combine(str, sub_str, idx + 1);
}

int main() {
  string str = "abc";
  cout << "permute: " << endl;
  permute(str, 0);

  cout << "\ncombine: " << endl;
  string sub_str;
  combine(str, sub_str, 0);

  return 0;
}
